package com.hardy.basic;

import java.util.*;

/**
 * Author: Hardy
 * Date:   2021/3/4
 * Description:
 **/
public class App {

    static class LRU<K, V> extends LinkedHashMap<K, V> {
        private final int maxSize;

        static final float DEFAULT_LOAD_FACTOR = 0.75f;

        public LRU(int maxSize) {
            super(0, DEFAULT_LOAD_FACTOR, true);
            this.maxSize = maxSize;
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > maxSize;
        }
    }

    // 一致性hash
    static class ConsistentHash {

        List<String> nodes;
        TreeMap<Integer, String> vnodes;

        public ConsistentHash() {
            this.nodes = Arrays.asList("10.0.0.1", "10.0.0.2", "10.0.0.3");
            this.vnodes = new TreeMap();
            init();
        }

        void init() {
            for (String node : nodes) {
                for (int i = 0; i < 10; i++) {
                    String vnode = node + "&&" + i;
                    vnodes.put(hash(vnode), node);
                }
            }
        }

        int hash(String s) {
            return s.hashCode();
        }

        String getNode(String key) {
//            int hash = hash(key);
            int hash = 1106708434;
            Map.Entry<Integer, String> entry = vnodes.ceilingEntry(hash);
            if (entry != null) return entry.getValue();
            return vnodes.firstEntry().getValue();
        }
    }


    static class LFUNode {
        int c;
        long nano;
        int k;
        int v;

        LFUNode prev;
        LFUNode next;

        public LFUNode(int k, int v) {
            this.c = 0;
            this.nano = 0;
            this.k = k;
            this.v = v;
        }
    }

    static class LFU {
        Map<Integer, LFUNode> cache;

        LFUNode head;
        LFUNode tail;

        int size = 0;
        int capacity;

        public LFU(int capacity) {
            this.capacity = capacity;
            this.cache = new HashMap<>();
        }

        public int get(int key) {
            LFUNode node = cache.get(key);
            if (node == null) return -1;
            recompare(node);
            return node.v;
        }

        public void put(int key, int value) {
            LFUNode node = cache.get(key);
            if (node == null) {
                if (size == capacity) {
                    cache.remove(tail.k);
                    if (size <= 1) {
                        tail = null;
                        head = null;
                    } else {
                        tail = tail.prev;
                        tail.next.prev = null;
                        tail.next = null;
                    }
                    size--;
                }
                node = new LFUNode(key, value);

                if (size == 0) {
                    head = node;
                    tail = node;
                } else {
                    node.prev = tail;
                    tail.next = node;
                    tail = node;
                }
                cache.put(key, node);
                size++;
            } else {
                node.v = value;
            }
            recompare(node);
        }

        void recompare(LFUNode node) {
            node.nano = System.nanoTime();
            node.c++;

            if (size == 1) return;

            // 查找
            LFUNode cnode = node;
            while (node != null && node.prev != null) {
                if (node.prev.c > cnode.c) break;
                if (node.prev.nano > cnode.nano) break;
                node = node.prev;
            }

            // 调整插入
            if (cnode == node) return;

            if (cnode == tail) {
                tail = cnode.prev;
                tail.next = null;
            } else {
                cnode.prev.next = cnode.next;
                cnode.next.prev = cnode.prev;
            }

            cnode.next = node;
            cnode.prev = node.prev;
            node.prev = cnode;

            if (node == head) {
                head = cnode;
            } else {
                cnode.prev.next = cnode;
            }
        }
    }

    /**
     * Your LFUCache object will be instantiated and called as such:
     * LFUCache obj = new LFUCache(capacity);
     * int param_1 = obj.get(key);
     * obj.put(key,value);
     */
    public static void main(String[] args) {
        //LRU<Integer, Integer> lru = new LRU<>(2);
        //lru.put(1, 1);
        //lru.put(2, 2);
        //lru.get(1);
        //lru.put(3, 3);
        //lru.get(1);
        //lru.put(4, 4);

        //ConsistentHash chash = new ConsistentHash();
        //String aaa = chash.getNode("aaa");
        //String zzz = chash.getNode("zzz");
        //String ttt = chash.getNode("ttt");

        LFU lfu = new LFU(3);
        lfu.put(1, 1);
        lfu.put(2, 2);
        lfu.put(3, 3);
//        lfu.put(4, 4);
//        lfu.get(4);
//        lfu.get(3);
//        lfu.get(2);
//        lfu.get(1);
//        lfu.put(5, 5);
//        lfu.get(1);
//        lfu.get(2);
//        lfu.get(3);
//        lfu.get(4);
//        lfu.get(5);
    }
}
